package lru;


import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.Map;

public class LFUDemo {

         private Map<Integer, Integer> vals; // 存储缓存数据
         Map<Integer, Integer> counts; // 存储每个缓存数据的访问次数
         Map<Integer, LinkedHashSet<Integer>> lists; // 存储每个访问次数对应的缓存数据列表
         int capacity; // 缓存容量
         int minCount; // 最小访问次数


        public LFUDemo(int capacity) {
            this.capacity = capacity;
            this.minCount = 0;
            this.vals = new HashMap<>();
            this.counts = new HashMap<>();
            this.lists = new HashMap<>();
            lists.put(1, new LinkedHashSet<>());
        }

        public int get(int key) {
            if (!vals.containsKey(key)) {
                return -1;
            }
            int count = counts.get(key);
            counts.put(key, count + 1);
            lists.get(count).remove(key); // 从原访问次数列表中移除
            if (count == minCount && lists.get(count).isEmpty()) {
                minCount++;
            }
            if (!lists.containsKey(count + 1)) {
                lists.put(count + 1, new LinkedHashSet<>());
            }
            lists.get(count + 1).add(key); // 加入更新后的访问次数列表
            return vals.get(key);
        }


        public void put(int key, int value) {
            if (capacity <= 0) {
                return;
            }

            if (vals.containsKey(key)) {
                vals.put(key, value);
                get(key);
                return;
            }

            if (vals.size() >= capacity) {
                int evictKey = lists.get(minCount).iterator().next(); // 移除最少访问次数的缓存数据
                vals.remove(evictKey);
                counts.remove(evictKey);
                lists.get(minCount).remove(evictKey);
            }

            vals.put(key, value);
            counts.put(key, 1);
            minCount = 1;
            lists.get(1).add(key);
        }


    public static void main(String[] args) {
        LFUDemo lfuDemo = new LFUDemo(3);
        lfuDemo.put(1,1);
        lfuDemo.put(2,2);
        lfuDemo.put(3,3);
        lfuDemo.get(2);
        lfuDemo.get(1);
        lfuDemo.put(4,4);
//        Map<Integer, Integer> vals = lfuDemo.vals;
//        Iterator<Map.Entry<Integer, Integer>> iterator = vals.entrySet().iterator();
//        while (iterator.hasNext()){
//            Map.Entry<Integer, Integer> next = iterator.next();
//            System.out.println(next.getKey());
//            System.out.println(next.getValue());
//        }

//        Map<Integer, Integer> vals = lfuDemo.counts;
//        Iterator<Map.Entry<Integer, Integer>> iterator = vals.entrySet().iterator();
//        while (iterator.hasNext()){
//            Map.Entry<Integer, Integer> next = iterator.next();
//            System.out.println(next.getKey());
//            System.out.println(next.getValue());
//        }


        Map<Integer, LinkedHashSet<Integer>> lists = lfuDemo.lists;
        Iterator<Map.Entry<Integer, LinkedHashSet<Integer>>> iterator1 = lists.entrySet().iterator();

        while (iterator1.hasNext()){
            Map.Entry<Integer, LinkedHashSet<Integer>> next = iterator1.next();
            Integer key = next.getKey();

            LinkedHashSet<Integer> value = next.getValue();
            for (int i = 0; i < value.size(); i++) {
                System.out.println(value);
            }




        }



    }
    }

